/*
实验2-5 约瑟夫问题
分数 25
作者 陈越
单位 浙江大学

编号为 1,2,3,⋯,n 的 n 个人按照顺时针方向围坐一圈。从第一个人开始按照顺时针方向从
1 开始报数，当报到指定的数 m 时，报 m
的人出列。再从他顺时针方向的下一位人开始重新从 1 开始报数，报到 m
的人出列，如此下去，直到所有人都出列。请设计算法用单向循环链表模拟约瑟夫问题的出列过程，输出出列的顺序。
函数接口定义：

List JosephusProblem( int n, int m );

其中List结构定义如下：

typedef struct ListNode *Position; /* 指针即结点位置
struct ListNode {
    ElemSet data;  /* 存储数据
    Position next;  /* 线性表中下一个元素的位置
};

typedef struct HeadNode *List;
struct HeadNode {
    Position head;  /* 单链表头指针
    int length;    /* 表长
};

函数接口定义中，n 是总人数，m
是出列间隔的人数。该函数须将出列人的编号按照出列顺序存
为带空头结点的单链表，并返回该链表的表头指针。

输入样例：

10 3

输出样例：

3 6 9 2 7 1 8 5 10 4
*/

#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet;
typedef struct ListNode *Position; /* 指针即结点位置 */
struct ListNode {
    ElemSet data;  /* 存储数据 */
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *List;
struct HeadNode {
    Position head; /* 单链表头指针 */
    int length;    /* 表长 */
};

List JosephusProblem(int n, int m);

void PrintList(List list) { /* 顺序输出链表结点数据 */
    Position p;

    p = list->head->next; /* p指向第1个结点 */
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
}
int main(void) {
    List list;
    int n, m;
    scanf("%d %d", &n, &m);
    list = JosephusProblem(n, m);
    PrintList(list);
    return 0;
}
/* 你的代码将被嵌在这里 */

List new_list(int n) {
    List list;
    Position tail, new_node;
    int i;

    list = (List)malloc(sizeof(struct HeadNode));
    list->head = (Position)malloc(sizeof(struct ListNode)); /* 创建空头结点 */
    list->length = n;
    tail = list->head; /* 初始化尾指针 */
    for (i = 1; i <= n; i++) {
        new_node = (Position)malloc(sizeof(struct ListNode));
        new_node->data = i;
        new_node->next = NULL;
        tail->next = new_node; /* 插入表尾 */
        tail = new_node;
    }
    tail->next = list->head->next; /* 首尾相连 */
    return list;
}

List JosephusProblem(int n, int m) {
    
    Position tail, new_node, p, q;
    int i, j;

    List list = new_list(n);

    p = list->head->next;          /* p指向第1个结点 */
    for (i = 1; i <= n; i++) {
        for (j = 1; j < m - 1; j++) {
            p = p->next;
        }
        q = p->next;
        p->next = q->next;
        printf("%d ", q->data);
        free(q);
        p = p->next;
    }
    list->head->next = NULL;
    return list;
}